package leetcode.dandiaostk;

public class A316 {
    public static String removeDuplicateLetters(String s) {
        int length=s.length();
        int[] num=new int[26];
int[] vis=new int[26]; //vis[i]==1表示被访问过
StringBuilder stk=new StringBuilder();
         //记录元素个数
        for(int i=0;i< s.length();i++){
            char cur=s.charAt(i);
            num[cur-'a']++;
        }
        //元素进栈，如果比栈顶小，并且栈顶对于字母还有，那么栈顶出，直到栈顶元素比当前元素还小---入栈---对应数目减1
        //如果比栈顶大，入栈
for(int i=0;i<length;i++){
    char cur=s.charAt(i);
    num[cur-'a']--;
    //如果该元素在栈中了，跳过
    if(vis[cur-'a']==1)continue;



    //如果栈为空或者栈顶元素小于该元素，该元素入栈
    if(stk.length()==0||cur- stk.charAt(stk.length()-1)>0){
        stk.append(cur);//入栈
        vis[cur-'a']=1;//标记为该元素在栈中
    }
    //如果比栈顶元素小或者和栈顶元素相等
    else{
        //栈不为空且栈顶元素大于该元素，且栈顶元素后续还有，则栈顶元素出栈
        while(stk.length()>0&&stk.charAt(stk.length()-1)>cur&&num[stk.charAt(stk.length()-1)-'a']!=0){//比栈顶元素小或者和栈顶元素相等且栈顶元素后续还有，则栈顶元素出
            vis[stk.charAt(stk.length()-1)-'a']=0;//标记为没在栈中
            //出栈
            stk.deleteCharAt(stk.length()-1);
        }
     //该元素入栈
        stk.append(cur);
        vis[cur-'a']=1;//标记为入栈了
    }
}
        String res= stk.toString();
return res;
    }

    public static void main(String[] args) {
        String s="cbacdcbc";
        String s1 = removeDuplicateLetters(s);
        System.out.println(s1);
    }
}
